This crate implements the Hopcroft-Karp algorithm to find maximum unweighted matchings in bipartite graph.
Basic usage
The crate provides the function hopcroft_karp::matching
(plus a few variants) which takes as input a vector of edges (encoding the bipartite graph) and returns a maximum matching as a vector of edges.
Example usage:
use matching;
matching
is generic over the vertex type, the trait bounds are Hash + Copy + Eq
. For types where the copy operation
is potentially expensive (e.g. strings) the crate provides the function hopcrof_karp::matching_mapped
which internally
maps the vertices onto integers and mostly avoids copying the type.
use ;
Variants
The crate exposes further methods geared towards specific use-cases. If only the size of the matching is needed, hopcroft_karp::matching_size
avoids constructing the solution matching. If only a matching above a certain size is needed,
hopcroft_karp::bounded_matching
returns a result as soon as the matching size lies above the provided bound.
These variants come in all possible combinations, e.g. hopcroft_karp::bounded_matching_mapped_size
returns the size of
a matching above the provided bound (or a smaller value if the bound is larger than the maximum matching) while internally re-mapping the graph's vertices to avoid expensive copy operations.